The internal representation

Given a tree, the corresponding TEXtree is a box containing the ``drawing'' of the tree, together with some additional information about the contour of the tree. The reference point of a TEXtree-box is always in the root of the tree. The height, depth, and width of the box of a TEXtree are of no importance in this context.

The additional information about the contour of the tree is stored in some registers for numbers and dimensions and is needed in order to put subtrees together to form a larger tree. loff is an array of dimensions which contains for each level of the tree the horizontal offset between the left end of the leftmost node at the current level and the left end of the leftmost node at the next level. lmoff holds the horizontal offset between the root and the leftmost node of the whole tree. lboff holds the horizontal offset between the root and the leftmost node at the bottom level of the tree. Finally, ltop holds the distance between the reference point of the tree and the leftmost end of the root. The same is true for roff, rmoff, rboff, and rtop; just replace ``left'' by ``right''. Finally, height holds the height of the tree, and type holds the geometric shape of the root of the tree. Figure [*] shows an example TEXtree, i.e. a tree drawing and the corresponding additional information.

Figure: A TEXtree consists of the drawing of the tree and the additional information. The width of the dots is 4pt, the minimal separation between adjacent nodes is 16pt, making for a distance of 20pt center to center. The length of the small rule labelling one of the nodes is 5pt. The column left (right) of the tree drawing is the array loff (roff), describing the left (right) contour of the tree. At each level, the dimension given is the horizontal offset between the border at the current and at the next level. The offset between the left border of the root node and the leftmost node at level 1 is -10pt, the offset between the right border of the root node and the rightmost node at level 1 is 15pt, etc.
\begin{figure}\vspace{1\baselineskip}\centering \begin{Tree} \node{\external\typ... ...moff:~20pt, lboff:~10pt, rboff:~10pt. \par \vspace{1\baselineskip}\end{figure}

Given two TEXtrees A and B, how can a new TEXtree C be built that consists of a new root and has A and B as subtrees? An example is given in Figure [*].

Figure: The TEXtrees A and B are combined to form the larger TEXtree C. The small table gives the history of computation for totsep and currsep.
\begin{figure}\vspace{1\baselineskip}\centering \begin{Tree} \node{\external\typ... ...t\\ 3&40pt&16pt\\ \hline \end{tabular} \vspace{1\baselineskip}\end{figure}

First we determine which tree is higher; this is B in the example. Then we have to compute the minimal distance between the roots of A and B, such that at all levels of the trees there is free space of at least minsep between the trees when they are drawn side by side. For this purpose we keep track of two values, totsep and currsep. The variables totsep and currsep hold the total distance between the roots and the distance between the rightmost node of A and the leftmost node of B at the current level. In order to calculate totsep and currsep, we start at level 0 and visit each level of the trees until we reach the bottom level of the smaller tree; this is A in our example.

At level 0, the distance between the roots of A and B should be at least minsep. Therefore, we set $\it totsep\/$ : = $\it minsep\/$ + $\it rtop\/$($\it A\/$) + $\it ltop\/$($\it B\/$) and $\it currsep\/$ : = $\it minsep\/$. Using $\it roff\/$($\it A\/$) and $\it loff\/$($\it B\/$), we can proceed to calculate currsep for the next level. If $\it currsep\/$ < $\it minsep\/$, we have to increase totsep by the difference and update currsep. This process is iterated until we reach the lowest level of A. Then totsep holds the final distance between the nodes of A and B, as calculated by the RT algorithm. If the root of C is a significant node, then the additional space , which is 0pt by default, is added to totsep. However, the approach of synthesizing drawings from simple graphics characters allows only a finite number of orientations for the tree edges; therefore, totsep must be increased slightly to fit the next orientation available.

Now we are ready to construct the box of TEXtree C. Simply put A and B side by side, with the reference points totsep units apart, insert a new node above them, and connect the parent and children by edges.

Next, we update the additional information for C. This can be done by using the additional information for A and B. Note that most components of $\it roff\/$($\it C\/$) and $\it lroff\/$($\it C\/$) are the same as in the higher tree, which is B in our case. So, if we can avoid moving this information around, we only have to access $\it height\/$($\it A\/$) + $\it const\/$ many counters in order to update the additional information for C. This implies that we can apply the same argument as in [15], which gives us a running time of O(N) for drawing a tree with N nodes.

Therefore, we must carefully design the storage allocation for the additional information of TEXtrees in order to fulfill the following requirements: If a new tree is built from two subtrees, the additional information of the new tree should share storage with its larger subtree. Organizational overhead, that is, pointers which keep track of the locations of different parts of additional information, must be avoided. This means that all the additional information for one TEXtree should be stored in a row of consecutive dimension registers such that only one pointer granting access to the first element in this row is needed. On the other hand, each parent tree is higher and therefore needs more storage than its subtrees. So we must ensure that there is always enough space in the row for more information.

The obvious way to fulfill these requirements is to use a stack and to allow only the topmost TEXtrees of this stack to be combined into a larger tree at any time. This leads to the following register allocation: A subsequent number of box registers contains the treeboxes of the subtrees in the stack. A subsequent number of token registers contains the type information for the nodes of the subtrees in the stack. For each subtree in the stack, a subsequent number of dimension registers contains the contour information of the subtree. The ordering of these groups of dimension registers reflects the ordering of the subtrees in the stack. Finally, a subsequent number of counter registers contains the height and the address of the first dimension register for each subtree in the stack. Four address counters store the addresses of the last treebox, type information, height, and address of contour information. A sketch of the register organization for a stack of TEXtrees is provided in Figure [*].

Figure: lasttreebox, lasttreeheight, lasttreeinfo, lasttreetype contain pointers to treebox(n) treeheight(n), lmoff(n), type(n), diminfo(i) contains a pointer to lmoff(i). Unused dimension registers are allowed between the dimension registers of subsequent trees. The counter registers lasttreebox,...,diminfo(n) serve as a directory mechanism to access the TEXtrees on the stack.
\begin{figure}\vspace{1\baselineskip}Dimension registers\\ {\it lmoff\/}(1) {\i... ...t type\/}(1) \dots\ {\it type\/}($n$) \par \vspace{1\baselineskip}\end{figure}

When a new node is pushed onto the stack, the treebox, type information, height, address of contour information, and contour information are stored in the next free registers of the appropriate type, and the four address counters are updated accordingly.

When a new tree is formed from the topmost subtrees on the stack, the treebox, type information, height, and address of contour information of the new tree are sorted in the registers formerly used by the bottommost subtree that has occured in the construction step, and the four address registers are updated accordingly. This means that these informations for the subtrees are no longer accessible. The contour information of the new subtree is stored in the same registers as the contour information of the larger subtree used in the construction, apart from the left and right offset of the root to the left and right child, which are stored in the following dimension registers. That means that gaps can occur between the contour information of subsequent subtrees in the stack, namely when the right subtree, which is on a higher position on the stack, is higher than the left one. In order to avoid these gaps, the user can specify an option \lefttop when entering a binary node, which makes the topmost tree in the stack the left subtree of the node.

This stack concept also has consequences for the design of the user interface that is discussed in Section [*].